package com.wyw.leetcode.learning.medium;

/**
 * leetcode topic 189
 * 旋转数组
 *
 * @Author Mr Wu （yewen.wu.china@gmail.com）
 * @Date 2021/11/4 15:35
 */
public class Topic189 {
    public static void main(String[] args) {
//        int[] nums = {-1,0,3,5,9,12};
        int[] nums = {1,2,3,4,5,6,7};
//        int[] nums = {-1};
//        int[] nums = {1,2};
//        rotate1(nums, 3);
//        rotate2(nums, 3);
        rotate3(nums, 3);
        rotate4(nums, 3);
    }

    /**
     * 时间复杂度： O(n)O(n)，其中 nn 为数组的长度。
     * 空间复杂度： O(n)O(n)。
     */
    public static void rotate1(int[] nums, int k) {
        int[] temp = nums.clone();
        for (int i = 0; i < nums.length; i++) {
            int j = i - k;
            while (j < 0) {
                j = (nums.length + j) % nums.length;
            }
            nums[i] = temp[j % nums.length];
        }
    }

    public static void rotate2(int[] nums, int k) {
        int n = nums.length;
        int[] newArr = new int[n];
        for (int i = 0; i < n; ++i) {
            newArr[(i + k) % n] = nums[i];
        }
        System.arraycopy(newArr, 0, nums, 0, n);
    }

    /**
     * 时间复杂度：O(n)O(n)，其中 nn 为数组的长度。每个元素只会被遍历一次。
     *
     * 空间复杂度：O(1)O(1)。我们只需常数空间存放若干变量
     */
    public static void rotate3(int[] nums, int k) {
        int n = nums.length;
        k = k % n;
        int count = gcd(k, n);
        for (int start = 0; start < count; ++start) {
            int current = start;
            int prev = nums[start];
            do {
                int next = (current + k) % n;
                int temp = nums[next];
                nums[next] = prev;
                prev = temp;
                current = next;
            } while (start != current);
        }
    }

    public static int gcd(int x, int y) {
        return y > 0 ? gcd(y, x % y) : x;
    }

    /**
     *时间复杂度：O(n)O(n)，其中 nn 为数组的长度。每个元素被翻转两次，一共 nn 个元素，因此总时间复杂度为 O(2n)=O(n)O(2n)=O(n)。
     *
     * 空间复杂度：O(1)O(1)。
     */
    public static void rotate4(int[] nums, int k) {
        k %= nums.length;
        reverse(nums, 0, nums.length - 1);
        reverse(nums, 0, k - 1);
        reverse(nums, k, nums.length - 1);
    }

    public static void reverse(int[] nums, int start, int end) {
        while (start < end) {
            int temp = nums[start];
            nums[start] = nums[end];
            nums[end] = temp;
            start += 1;
            end -= 1;
        }
    }


}
